#include <queue>
#include <set>

using namespace std;

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        multiset<int, greater<>> set;
        queue<multiset<int, greater<>>::iterator> queue;
        queue.push(set.insert(nums[0]));
        int ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int max_sum = max(*set.begin() + nums[i], nums[i]);
            queue.push(set.insert(max_sum));
            if (set.size() > k) {
                set.erase(queue.front());
                queue.pop();
            }
            ans = max(ans, *set.begin());
        }
        return ans;
    }
};